package com.wtgroup.demo.leetcode.q024_两两交换链表中的节点;

import com.wtgroup.demo.common.bean.LinkNode;

/**
 * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 * @author 60906
 * @date 2021/5/16 18:16
 */
public class Q024 {

    class Solution_Rec {
        public LinkNode swapPairs(LinkNode head) {
            return func(head);
        }

        LinkNode func(LinkNode h) {
            if (h == null || h.next == null) {
                return h;
            }

            // 2 + (n-2)
            /*ListNode post = func(h.next.next);
            ListNode newHead = h.next;
            h.next.next = null;
            h.next = null;
            newHead.next = h;
            newHead.next.next = post;*/

            // 简化
            LinkNode newHead = h.next;
            h.next = func(newHead.next);
            newHead.next = h;

            return newHead;
        }
    }

    class Solution_Iter {
        public LinkNode swapPairs(LinkNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            LinkNode dummyHead = new LinkNode();
            LinkNode tail = dummyHead;
            LinkNode cur = head;
            LinkNode next = null;
            while (cur != null && cur.next != null) {
                tail.next = cur.next;
                next = cur.next.next;
                tail.next.next = cur;
                tail = cur;
                cur = next;
            }
            // 最后一个单节点 or null
            tail.next = cur;
            return dummyHead.next;
        }
    }

}
